package practise.alogrithm.hundredInterviewQuestions.secondTime;

import practise.alogrithm.hundredInterviewQuestions.Utils.LinkedListBuilder;
import practise.alogrithm.hundredInterviewQuestions.Utils.ListNode;
import practise.alogrithm.hundredInterviewQuestions.Utils.TreeBuilder;
import practise.alogrithm.hundredInterviewQuestions.Utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by Richard on 7/25/2014.
 */
public class FindSumInTree {
    public Integer  findSumEveryPath(TreeNode treeNode, Integer previousSum, Integer expectSum,List<Integer> previousPath,List<List<Integer>> result,boolean isHead){
        //exist condition start
        if(treeNode==null){
            return 0;
        }
        if(treeNode.getLeft()==null && treeNode.getRight()==null){
            if(previousSum+treeNode.getValue()!=expectSum){
                return previousSum+treeNode.getValue();
            }
        }
        //exist condition end


        previousPath.add(treeNode.getValue());
        int sum = previousSum+treeNode.getValue();
        //from previous, compute the value from previous
        if(sum==expectSum){
            if(previousPath==null){
                previousPath= new ArrayList<>();
            }

            result.add(previousPath);
        }
        else{
             findSumEveryPath(treeNode.getLeft(),sum,expectSum,new ArrayList<>(previousPath),result,false);
            findSumEveryPath(treeNode.getRight(),sum,expectSum,new ArrayList<>(previousPath),result,false);

        }

        //from current, we start a new path calculate for every node, but as we already enter from head in the beginning
        //we should not enter it one more time

        int nodeSum=0;
        if(!isHead) {//note, when current is head, we should not enter the recursive twice
            sum = treeNode.getValue();
            previousPath = new ArrayList<>();
            previousPath.add(treeNode.getValue());
            if (sum == expectSum) {
                result.add(previousPath);
            } else {
                List<Integer> rightBranch = new ArrayList<>(previousPath);
                nodeSum =
                        findSumEveryPath(treeNode.getLeft(), sum, expectSum, new ArrayList<>(previousPath), result, isHead) +
                                findSumEveryPath(treeNode.getRight(), sum, expectSum, rightBranch, result, isHead) + treeNode.getValue();
                // cannot combine the sum un-cross node with cross node together, as if we want to sum the nodes from every path which can cross the node
                //we need another container to save all the possible path from a any sub-root
//            if(nodeSum==expectSum){
//                List<Integer> crossBranch = new ArrayList<>();
//                crossBranch.addAll(previousPath);
//                crossBranch.add(treeNode.getValue());
//                crossBranch.addAll(rightBranch);
//            }
            }
        }
        return nodeSum;
    }

    public void sumFromRoot(TreeNode treeNode,  Integer sum,Integer expect,List<Integer> tempResult, List<List<Integer>> result){
        if(treeNode==null){
            return ;
        }
        sum = sum+treeNode.getValue();
        tempResult.add(treeNode.getValue());
        if(sum==expect){
             result.add(tempResult);
            return;
        }
        if(sum>expect){
            return;
        }
         sumFromRoot(treeNode.getLeft(),sum,expect,new ArrayList<>(tempResult),result);
        sumFromRoot(treeNode.getRight(),sum,expect,new ArrayList<>(tempResult),result);
    }


    public static void main(String[] args){
        TreeNode treeNode = TreeBuilder.createTreeByArrayInWidth(new int[]{10,5,12,4,7,1,1,13});
        List<List<Integer>> result = new ArrayList<>();
        FindSumInTree findSumInTree = new FindSumInTree();
        findSumInTree.findSumEveryPath(treeNode, 0, 22, new ArrayList<>(), result,true);
        result.size();
        System.out.println(result);
        result = new ArrayList<>();
        findSumInTree.sumFromRoot(treeNode,0,22,new ArrayList<>(),result);
        result.size();

    }
}
